// https://leetcode.cn/problems/n-queens/

// 题干：按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
//      n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
//      给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
//      每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

// 示例：输入：n = 4
//       输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

// 碎语：重点在于如何剪枝，考虑一行一行的摆放皇后比较符合常理
//       逻辑很简洁明了，但是代码的转化能力是关键
//       判断是否要剪枝的时候，可以三层循环判断（列，主对角线，副对角线）
//       当一个正方形有边长为n的时候，对角线为2*n-1条
//       也可以采用bool row[i] ; bool col[i] ; bool dig1[i] ; bool dig2[i]
//       注意对角线的映射关系，纵坐标减去横坐标为定值
//       y=x+b,y-x=b为定值 ； y=-x+b,y+x=b为定值
//       数组越界问题，加上偏移量就行

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    bool checkCol[10], checkDig1[20], checkDig2[20];
    vector<vector<string>> ret;
    vector<string> path;
    int n;
public:
    vector<vector<string>> solveNQueens(int _n)
    {
        n = _n;
        memset(checkCol, 0, sizeof(checkCol));
        memset(checkDig1, 0, sizeof(checkDig1));
        memset(checkDig2, 0, sizeof(checkDig2));

//        std::string str1 = "Hello";
//        std::string str2 = " World";
//        str1.append(str2);
        path.resize(n); // 有n行,先全部赋予'.'
        for (int i = 0 ; i < n ; i++){
            path[i].append(n, '.'); // append用于在字符串后续接上新字符
        }

        dfs(0);

        return ret;

    }

    void dfs(int row)
    {
        if (row == n){
            ret.push_back(path);
            return ;
        }

        for (int i = 0 ; i < n ; i++){ // i代表列数
            if (!checkCol[i] && !checkDig1[row - i + n] && !checkDig2[row + i]){
                checkCol[i] = true, checkDig1[row - i + n] = true, checkDig2[row + i] = true;
                path[row][i] = 'Q'; // 这就代表已经放下了

                dfs(row + 1); // 递归下一层
                checkCol[i] = false, checkDig1[row - i + n] = false, checkDig2[row + i] = false;
                path[row][i] = '.'; // 回溯
            }
        }

    }
};

int main()
{
    Solution sol;

    vector<vector<string>> index = sol.solveNQueens(4);
    for (const auto& strAry : index){
        for (const auto& str : strAry){
            cout << str << " ";
        }
        cout << endl;
    }
    
    return 0;
}





